import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 描述：二分搜索树的数据结构定义
 * 定义一个泛型，并且这个泛型必须拥有可比较性。
 * E必须extends，必须满足Comparable这个接口
 *
 * @author WangB
 * create 2018-10-20-19:46
 */
public class BST<E extends Comparable <E>>{
    /**
     * 在二分搜索树中建立了一个节点类，声明为private
     * 意思就是用户不必关心我这个Node是如何实现的
     */
    private class Node{
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }


    private Node root;//二分搜索树需要拥有一个根节点
    private int size;//二分搜索树的大小

    /**
     * 对二分搜索树进行初始化。
     * size = 0
     * root 根节点设置成null
     * 这样写的跟默认的构造函数是一样的
     */
    public BST( ) {
        root = null;
        size = 0;
    }

    public int getSize( ) {
        return size;
    }

    public boolean isEmpty( ) {
        return size == 0;
    }


    /**
     * 二分搜索树中插入一个元素。递归的调用下面的add方法
     *
     * @param e
     */

    public void add(E e) {
        root = add ( root , e );
    }

    /**
     * 向以node为根的树中插入e
     *
     * @param node
     * @param e
     */
    private Node add(Node node , E e) {
        if ( node == null ) {
            size++;
            return new Node ( e );
        }

        if ( e.compareTo ( node.e ) < 0 )
            node.left = add ( node.left , e );
        else if ( e.compareTo ( node.e ) > 0 )
            node.right = add ( node.right , e );
        return node;
    }

    /**
     * 查询二分搜索树是否包括元素
     *
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return contains ( root , e );
    }

    /**
     * 递归的查询。
     *
     * @param node
     * @param e
     * @return
     */
    private boolean contains(Node node , E e) {
        if ( node == null )
            return false;
        if ( e.compareTo ( node.e ) == 0 )
            return true;
        else if ( e.compareTo ( node.e ) < 0 )
            return contains ( node.left , e );
        else //e.compareTo(Node.e)>0
            return contains ( node.right , e );
    }

    /**
     * 二叉树的前序遍历
     */
    public void preOrder( ) {
        preOrder ( root );
    }

    /**
     * 前序遍历以node为根的二分搜索树递归算法
     *
     * @param node
     */
    private void preOrder(Node node) {
        if ( node == null )
            return;
        System.out.println ( node.e );
        preOrder ( node.left );
        preOrder ( node.right );
    }

    /**
     * 前序遍历的非递归写法
     */
    public void preOrderNR(){
        Stack<Node> stack = new Stack <> ();
        stack.push (root);
        while (!stack.isEmpty ()){
            Node cur = stack.pop ();
            System.out.println (cur.e);
            if(cur.right != null)
                stack.push (cur.right);
            if(cur.left != null)
                stack.push (cur.left);
        }

    }
    /**
     * 二分搜索树的中序遍历
     */
    public void inOrder(){
        inOrder (root);
    }

    /**
     * 中序遍历的递归过程
     * @param node
     */
    private void inOrder(Node node){
        if(node == null)
            return;
        inOrder (node.left);
        System.out.println (node.e);

        inOrder (node.right);
    }

    /**
     * 二叉树的后序遍历
     */
    public void postOrder( ) {
        postOrder ( root );
    }

    /**
     * 前序遍历以node为根的后续遍历算法
     *
     * @param node
     */
    private void postOrder(Node node) {
        if ( node == null )
            return;

        postOrder ( node.left );
        postOrder ( node.right );
        System.out.println ( node.e );
    }

    public void levelOrder(){
        //因为queue是一个接口，因此需要给一个具体的实现方式。
        Queue<Node> q = new LinkedList <> ();
        q.add(root);
        while (!q.isEmpty ()){
            Node cur = q.remove ();
            System.out.println (cur.e);
            if(cur.left != null)
                q.add (cur.left);
            if(cur.right != null)
                q.add (cur.right);
        }
    }

    /**
     * 获得最小值。
     * @return
     */
    public E minimum(){
        if(size == 0 )
            throw new IllegalArgumentException ("bst is empty");
        return minimum (root).e;
    }

    /**
     * 获得最小值的递归部分
     * @param node
     * @return
     */
    private Node minimum(Node node){
        if(node.left == null)
            return node;
        else
            return minimum (node.left);

    }

    /**
     * 获得bst的最大值。
     * @return
     */
    public E maximum(){
        if(size == 0 )
            throw new IllegalArgumentException ("bst is empty");
        return maximum (root).e;
    }

    /**
     * 获得bst的最大值的递归部分。
     * @param node
     * @return
     */
    private Node maximum(Node node){
        if(node.right == null)
            return node;
        else
            return maximum (node.right);
    }

    /**
     * 从二分搜索树中删除最小节点，并返回值。
     * @return
     */
    public E removeMin(){
        E ret = minimum ();//获得最小值
        root = removeMin (root);
        return ret;
    }

    /**
     * 删除掉以node为节点的二分搜索数的最小节点
     * 并返回删除节点后的新的二分搜索数的根
     * @param node
     * @return
     */
    private Node removeMin(Node node){
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin (node.left);
        return node;
    }

    /**
     * 删除任意节点。这个删除了之后，将该点的后继替换了。
     * 也可以用该点的前驱来替换。
     * @param e
     */
    public void remove(E e){
        root = remove (root,e);
    }

    /**
     * 删除以node为根节点的bst中值为e的节点，递归算法
     * @param node
     * @param e
     * @return
     */
    private Node remove(Node node,E e){
        if(node == null)
            return null;
        if(e.compareTo (node.e)<0){
            node.left = remove (node.left,e);
            return node;
        }else if(e.compareTo (node.e) > 0){
            node.right = remove(node.right,e);
            return node;
        }else{ //e==node.e
            if(node.left == null){//待删除的节点左子树为空
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }

            if(node.right == null){//待删除的节点的右子树为空
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            //待删除节点左右子树都不空的时候。
            //找到比这个节点大的节点的最小节点，也就是后继。也就是待删除节点右子树的最小节点。
            // 用这个节点顶替待删除节点的位置。
            Node successor = minimum (node.right);//node的后继
            successor.right = removeMin (node.right);
            successor.left = node.left;
            node.left=node.right = null;
            return successor;
        }

    }

    @Override
    public String toString( ) {
        StringBuilder res = new StringBuilder ();
        genrateBSTString ( root , 0 , res );
        return res.toString ();
    }

    private void genrateBSTString(Node node , int depth , StringBuilder res) {
        if ( node == null ){
            res.append ( genrateDepthString ( depth ) + "null\n" );
            return;
        }

        res.append ( genrateDepthString ( depth ) + node.e + "\n" );
        genrateBSTString ( node.left,depth+1,res );
        genrateBSTString ( node.right,depth+1,res );
    }

    /**
     * 用来表达二叉树的深度。
     * @param depth
     * @return
     */
    private String genrateDepthString(int depth) {
        StringBuilder res = new StringBuilder ();
        for ( int i = 0 ; i < depth ; i++ ) {
            res.append ( "--" );
        }
        return res.toString ();
    }

    public static void main(String[] args){


    }
}

